
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-05
 * Time: 9:20
 */

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null){
            return result;
        }
        // 利用一个栈和一个队列
        Stack<TreeNode> stack = new Stack<>();
        stack.push(pRoot);
        // 标记从左往右入队列, 还是从右往左入队列
        boolean flag = true;
        while (!stack.isEmpty()){
            // 队列要么每次进入循环都 new 一个, 要么每层使用完就清空
            // 不然 stack 中会一直有节点, 陷入死循环
            Queue<TreeNode> queue = new LinkedList<>();
            ArrayList<Integer> temp = new ArrayList<>();
            int size = stack.size();
            for (int i = 0; i < size; i++) {
                TreeNode root = stack.pop();
                temp.add(root.val);
                // 找出入队列的顺序
                TreeNode first = flag ? root.left : root.right;
                TreeNode second = flag ? root.right : root.left;
                if(first != null){
                    queue.add(first);
                }
                if(second != null){
                    queue.add(second);
                }
            }
            // 不要忘了反转遍历方式
            flag = !flag;
            // 将这一层的结果放进所有的结果集中
            result.add(temp);
            // 把队列中的元素重新放入 栈中
            for (TreeNode node: queue) {
                stack.push(node);
            }
            // 注意放完后, 其实queue 已经清空了, 因为后面又 new 一个新的队列
        }
        return result;
    }
}
